前面我們提過了 Bubble sort，這次我們要來從題目來看另一種排序的演算法 —— Insertion Sort。

題目
使用下面這個函數將數列由小排到大

void insertionSort (const int sorted[], int sorted[], int len);

輸入輸出格式

Sol.
首先，先將資料分成已排序、未排序兩部分。在未排序的部分中，從第一筆資料開始跟已排序的相互比較，並插到適當的位置。這個情況由於是由小排到大，因此我們會從右至左比較。

[演算法] 插入排序法(Insertion Sort)
Comparison Sort: Insertion Sort(插入排序法)
這兩篇文章都有做一個詳盡的介紹，第一篇包含計算時間複雜度，有興趣的人可以參考！

Pseudocode

insertionSort：
	int temp = 0;
	int j = 0;
	// 每一個要處理的值就存為temp，並與已處理的部分做比較
	for i in range 0 ~ len
		temp = sorted[i];
		j = i - 1;
		// 判斷能否插入數值
		while (i 不是第 0 個數 且 temp < sorted[j]) 
            // 向右移
        	sorted[j + 1] = sorted[j];
			j--;
Main function：
	cin >> len;
	int* sorted = new int[len];
	輸入 sorted 所需存的資料

以上就是粗略的 insertion sort 啦！